package buildTree;

import util.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @program: javase
 * @description: 前序，中序构建二叉树
 * @author: luolidong
 * @create: 2021-06-18 10:09
 * @version: 1.0
 */
//
public class BuildTreeByPreInOrder {
    /**
    * @Description: 每次通过数组拆分
    * @Param: [preorder, inorder]
    * @return: util.TreeNode
    */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        //根据前序数组的第一个元素，就可以确定根节点
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 0; i < preorder.length; ++i) {
            //用preorder[0]去中序数组中查找对应的元素
            if (preorder[0] == inorder[i]) {
                //将前序数组分成左右两半，再将中序数组分成左右两半
                //之后递归的处理前序数组的左边部分和中序数组的左边部分
                //递归处理前序数组右边部分和中序数组右边部分
                int[] pre_left = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] pre_right = Arrays.copyOfRange(preorder, i + 1, preorder.length);
                int[] in_left = Arrays.copyOfRange(inorder, 0, i);
                int[] in_right = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                root.left = buildTree(pre_left, in_left);
                root.right = buildTree(pre_right, in_right);
                break;
            }
        }
        return root;

    }

    /**
    * @Description: 确定前序中序区间位置
    * @Param: [preorder, inorder]
    * @return: util.TreeNode
    */
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        TreeNode root = build(preorder, map, 0, preorder.length - 1, 0, inorder.length - 1);
        return root;
    }

    private TreeNode build(int[] preorder, Map<Integer, Integer> map
            , int preLeft, int preRight, int inLeft, int inRight) {
        //终止条件
        if (preLeft > preRight || inLeft > inRight) return null;
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
        int pIndex = map.get(rootVal);
        root.left = build(preorder, map, preLeft + 1, pIndex - inLeft + preLeft, inLeft, pIndex - 1);
        root.right = build(preorder, map, pIndex - inLeft + preLeft + 1, preRight, pIndex + 1, inRight);
        return root;
    }


    public static void main(String[] args) {
        int[] pre = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] in = new int[]{4, 2, 5, 1, 6, 3, 7};
        TreeNode node = new BuildTreeByPreInOrder().buildTree2(pre, in);
        System.out.println(node);
    }
}
